class Solution {
public:
	bool isValid(string s) {
		stack<int>stk;
		if (s.length() % 2) { return false; }
		for (int i = 0; i < s.length(); i++) {
			if (s[i] == '[') { stk.push(']'); }
			else if (s[i] == '(') { stk.push(')'); }
			else if (s[i] == '{') { stk.push('}'); }
			else if (stk.empty() || s[i] != stk.top()) { return false; }
			else { stk.pop(); }
		}
		if (!stk.empty()) { return false; }
		else { return true; }
	}
};